Knowledge, chance, and change [PhD Thesis]

1 Introduction 1
2 Epistemic logic 3
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Language and semantics . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Proof systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 General and common knowledge . . . . . . . . . . . . . . . . . . . 7
2.5 Bisimulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Strong completeness and disharmony 11
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 The in¯nitary proof system PDL! . . . . . . . . . . . . . . . . . . 12
3.3 Strong completeness: the canonical model for PDL! . . . . . . . . 16
3.4 Generalization to other modal logics . . . . . . . . . . . . . . . . 19
3.4.1 Epistemic logic . . . . . . . . . . . . . . . . . . . . . . . . 21
3.5 Comparison to other work . . . . . . . . . . . . . . . . . . . . . . 23
3.6 Program (dis)harmony . . . . . . . . . . . . . . . . . . . . . . . . 25
3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4 Information change 33
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.1.1 Muddy children . . . . . . . . . . . . . . . . . . . . . . . . 35
4.1.2 Byzantine generals . . . . . . . . . . . . . . . . . . . . . . 36
4.1.3 Sum and product . . . . . . . . . . . . . . . . . . . . . . . 37
4.1.4 Cluedo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.1.5 Lecture or Amsterdam . . . . . . . . . . . . . . . . . . . . 38
4.2 Multi-agent systems . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3 Dynamic epistemic logic . . . . . . . . . . . . . . . . . . . . . . . 42
4.3.1 Updating with programs . . . . . . . . . . . . . . . . . . . 43
4.3.2 Learning to preserve S5 . . . . . . . . . . . . . . . . . . . 47
4.3.3 Epistemic actions . . . . . . . . . . . . . . . . . . . . . . . 50
4.3.4 Changing modalities . . . . . . . . . . . . . . . . . . . . . 56
4.4 From action terms to action sentences . . . . . . . . . . . . . . . . 58
4.4.1 Action language . . . . . . . . . . . . . . . . . . . . . . . . 59
4.4.2 Dyadic hybrid epistemic logic . . . . . . . . . . . . . . . . 69
4.5 Where do we go? . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5 Intensional and statistical probability 77
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.2 Languages and Models . . . . . . . . . . . . . . . . . . . . . . . . 80
5.2.1 The intensional probability logic IPL . . . . . . . . . . . . 80
5.2.2 The statistical probability logic SPL . . . . . . . . . . . . . 82
5.3 The relation between IPL and SPL . . . . . . . . . . . . . . . . . . 84
5.4 The probabilistic epistemic logic PEL . . . . . . . . . . . . . . . . 86
5.4.1 Language and semantics . . . . . . . . . . . . . . . . . . . 86
5.4.2 Sample space assignments . . . . . . . . . . . . . . . . . . 88
5.4.3 The generalized statistical probability logic GSPL . . . . . 90
5.5 Toward correspondence theory for probability logics . . . . . . . . 94
5.5.1 Correspondences . . . . . . . . . . . . . . . . . . . . . . . 95
5.5.2 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6 Probabilistic dynamic epistemic logic 99
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.3 Language and semantics . . . . . . . . . . . . . . . . . . . . . . . 101
6.4 Reasoning about probability . . . . . . . . . . . . . . . . . . . . . 105
6.4.1 Building a Model . . . . . . . . . . . . . . . . . . . . . . . 105
6.4.2 Proof system, soundness and completeness . . . . . . . . . 108
6.5 Bisimulation for probabilistic dynamic epistemic logic . . . . . . . 114
6.6 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.7 Conclusion and further research . . . . . . . . . . . . . . . . . . . 119
7 The Monty Hall dilemma 121
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.2 A semantical analysis . . . . . . . . . . . . . . . . . . . . . . . . . 123
7.3 A syntactic analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 125
7.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
8 Mastermind 129
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
8.2 Game theoretic analysis . . . . . . . . . . . . . . . . . . . . . . . 130
8.3 A simple strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
8.4 Looking one step ahead . . . . . . . . . . . . . . . . . . . . . . . . 131
8.5 Empirical results . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
8.6 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
8.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
9 Trying to resolve the two-envelope problem 141
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
9.2 A purely logical paradox . . . . . . . . . . . . . . . . . . . . . . . 143
9.3 The two-envelope paradox . . . . . . . . . . . . . . . . . . . . . . 146
9.4 The two-envelope problem . . . . . . . . . . . . . . . . . . . . . . 146
10 Conclusion 149
Samenvatting 153
Bibliography 156
Index 169